package bin_tree.heap.leetcode;

import java.util.*;

/**
 * @author yuisama
 * @date 2023/03/31 21:25
 * 出现频次最高的前k个元素
 **/
public class Num347_TopKFreq {
    // 取大用小
    public int[] topKFrequent(int[] nums, int k) {
        // 局部内部类
        class Freq {
            int key; // 出现的元素
            int times; // 出现的频率
            Freq(int key, int times) {
                this.key = key;
                this.times = times;
            }
        }
        // 1.扫描nums数组，将每个元素和出现的次数保存到Map接口中
        Map<Integer,Integer> numTimes = new HashMap<>();
        for (int i : nums) {
//            numTimes.put(i,numTimes.getOrDefault(i,0) + 1);
            if (numTimes.containsKey(i)) {
                int value = numTimes.get(i);
                numTimes.put(i,value + 1);
            }else {
                numTimes.put(i,1);
            }
        }
        // 2.扫描Map接口，将出现频次最高的前k个Freq对象保存到优先级队列中
        Queue<Freq> queue = new PriorityQueue<>(new Comparator<Freq>() {
            @Override
            public int compare(Freq o1, Freq o2) {
                return o1.times - o2.times;
            }
        });
        for (Map.Entry<Integer,Integer> entry : numTimes.entrySet()) {
            queue.offer(new Freq(entry.getKey(),entry.getValue()));
            if(queue.size() > k) {
                queue.poll();
            }
        }
        // 3.从队列中取出这k个Freq的key值就是最终的结果
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = queue.poll().key;
        }
        return result;
    }
}